//https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=23262&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sour
//动态规划f(n) =2*f(n-1);
//动态规划：f(n) = f(n) +f(n-1) +f(n-2) +f(n-3) +f(n-4) +f(n-5) +...f(0);

#include <vector>
using namespace std;

class Solution {
  public:
    int jumpFloorII(int number) {
        vector<int> dp(number + 1);
        dp[1] = 0;
        dp[1] = 1;
        //依次乘2
        for (int i = 2; i <= number; i++)
            dp[i] = 2 * dp[i - 1];
        return dp[number];        
    
    }
};

#include <numeric>
class Solution2 {
  public:

    int jumpFloorII(int number) {
        vector<int> dp(number+1,0);
        dp[0] = 1;
        
        for (int i = 1; i <= number; i++) {
            auto cur_sum = std::accumulate(dp.begin(), dp.end(), 0);
            dp[i] = cur_sum;
        }
        return dp[number];        
    
    }
};